BST again

Time Limit: 10 Sec Memory Limit: 256 MB

Description

求有多少棵大小为n的深度为h的二叉树。（树根深度为0；左右子树有别；答案对1000000007取模）

Input

第一行一个整数T，表示数据组数。

以下T行，每行2个整数n和h。

Output

共T行，每行一个整数表示答案（对1000000007取模）

Sample Input

2
　2 1
　3 2

Sample Output

2
　4

HINT

1<=n<=600,0<=h<=600,1<=T<=10

Solution

我们运用DP来求解。

记f[i][j]表示点数为i，深度==j的方案数；
　　记g[i][j]表示点数为i，深度<=j的方案数。

转移的时候所以枚举一个点k作为根，那么左边显然就有k-1个点，右边就有i-k个点。

此时深度恰好为j-1的方案数为：
　　g[k-1][j-1] * g[i-k][j-1] - g[k-1][j-2] * g[i-k][j-2]。

所以我们就可以得到答案了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 1005;
const int MOD = 1e9 + 7;

int T;
int n, h;
int x, y;
int f[ONE][ONE], g[ONE][ONE];

struct pwoer
{
    int x, y;
}a[ONE];

int get()
{
    int res=1,Q=1;  char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

void Modit(int &a)
{
    if(a < 0) a += MOD;
    if(a >= MOD) a -= MOD;
}

int main()
{
    T = get();
    for(int i = 1; i <= T; i++)
        a[i].x = get(), a[i].y = get() + 1,
    n = max(n, a[i].x), h = max(h, a[i].y);

    f[0][0] = 1; for(int i = 0; i <= h; i++) g[0][i] = 1;
    f[1][1] = 1; for(int i = 1; i <= h; i++) g[1][i] = 1;
    for(int i = 2; i <= n; i++)
    {
        for(int j = 2; j <= i; j++)
            for(int k = 1; k <= i; k++)
                Modit(f[i][j] += (s64)g[k - 1][j - 1] * g[i - k][j - 1] % MOD - (s64)g[k - 1][j - 2] * g[i - k][j - 2] % MOD);

        g[i][0] = f[i][0];
        for(int j = 1; j <= h; j++)
            Modit(g[i][j] = g[i][j - 1] + f[i][j]);
    }    m

        for(int i = 1; i <= T; i++)
            printf("%d\n", f[a[i].x][a[i].y]);

}